////#include<iostream>
////#include<queue>
////
////using namespace std;
////
////int main()
////{
////    int m, n, k;
////    cin >> m >> n >> k;
////    queue<int> man, woman;
////    while (k--)
////    {
////        if (man.size() == 0)
////            for (int i = 1; i <= m; i++)
////                man.push(i);
////        if (woman.size() == 0)
////            for (int i = 1; i <= n; i++)
////                woman.push(i);
////        cout << man.front() << " " << woman.front() << endl;
////        man.pop(), woman.pop();
////    }
////    return 0;
////}
//
//#include<iostream>
//#include<vector>
//using namespace std;
//
//int main()
//{
//    vector<int> num;
//    int n, m; cin >> n >> m;
//    int i = 0, k = 1;
//    for (int j = 1; j <= n; j++)
//        num.push_back(j);
//    while (num.size() != 1)
//    {
//        i %= num.size();
//        if (k == m)
//        {
//            num.erase(num.begin() + i);
//            k = 1;
//        }
//        i++, k++;
//    }
//    cout << num[0];
//    return 0;
//}

//#include<iostream>
//#include<queue>
//#include<vector>
//using namespace std;
//
//struct cmp
//{
//    bool operator()(const pair<int, int>& a, const pair<int, int>& b)
//    {
//        return a.first > b.first || a.first == b.first && a.second > b.second;
//    }
//};
//
//priority_queue<pair<int, int>,vector<pair<int,int>>,cmp> q;
//
//int main()
//{
//    int n; cin >> n;
//    int tmp;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> tmp;
//        q.push({ tmp,i });
//    }
//    long long sum = 0, t = 0;
//
//    auto i = q.top();
//    q.pop();
//    cout << i.second;
//    sum += t;
//    t += i.first;
//
//    while (!q.empty())
//    {
//        auto i = q.top();
//        q.pop(); 
//        cout << " " << i.second;
//        sum += t;
//        t += i.first;
//    }
//    double ret = (double)sum / n;
//    printf("\n%.2lf", ret);
//    return 0;
//}

//#include<vector>
//#include<iostream>
//
//using namespace std;
//
//const int N = 1010;
//vector<int> qu;
//vector<int> retv;
//bool is[N];
//int t[N];
//int ret = 0x3f3f3f3f;
//int n;
//
//void dfs(int deep, int m, int last)
//{
//	if (m >= ret) 
//		return;
//	if (deep == n)
//	{
//		if (ret > m)
//		{
//			ret = m;
//			retv = qu;
//		}
//		return;
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		if (is[i]) continue;
//
//		is[i] = true;
//		qu.push_back(i);
//
//		dfs(deep + 1, m * 2 + t[i], i);
//
//		is[i] = false;
//		qu.pop_back();
//	}
//}
//
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//		cin >> t[i];
//	for (int i = 1; i <= n; i++)
//	{
//		is[i] = true;
//		int m = t[i];
//		qu.push_back(i);
//
//		dfs(1, m, i);
//
//		is[i] = false;
//		qu.pop_back();
//	}
//	cout << retv[0];
//	for (int i = 1; i < retv.size(); i++)
//		cout << " " << retv[i];
//	cout << endl;
//	printf("%.2lf", (double)ret / n);
//	return 0;
//}